package violencerecursion;

/**
 * @author tongchen
 * @create 2023-03-29 0:00
 */
public class Dp1MoneyNumber {
    public static void main(String[] args) {

    }
    public static int money(int[]arr,int target){
        return 0;
    }
    public static int process(int[]arr,int index,int rest,int[][]dp){
        if(dp[index][rest]!=-1){
            return dp[index][rest];
        }
        if(index== arr.length){
           dp[index][rest] = rest==0?1:0;
           return dp[index][rest];
        }
        int count=0;
        //进行递归：对于每个不同面值的货币，我们都有选择要不要或者选择几张的权利，只要还有余额
        for(int amount=0;amount*arr[index]<=rest;amount++){
            count+=process(arr, index+1, rest-amount*arr[index],dp);
        }
        dp[index][rest]=count;
        return dp[index][rest];
    }
}
